解决数组在动态数据操作中的根本局限性。

  • 数组昂贵的 $O(n)$ 修改时间带来的关键启示是，物理连续性是问题的根本原因，迫使我们在位置 $i$ 插入或删除元素时必须移动其他元素。
  • 如果我们的应用需要频繁且快速的修改（插入/删除），尽管数组具有 $O(1)$ 的随机访问能力，但其效率依然很低。
  • 为了实现最优的$O(1)$ 修改复杂度，我们必须找到一种顺序数据结构，从根本上改变元素的存储和排列方式。
  • 目标1：将逻辑与物理分离。逻辑顺序不应依赖于物理位置；元素应允许在内存中任意存放。
  • 目标2：动态大小。该结构必须能按需即时扩展或收缩，无需周期性地进行昂贵的 $O(n)$ 内存重分配。
  • 目标3：常数时间局部修改。一旦找到插入点 $i$，修改序列只需执行常数次指针操作（$O(1)$）。
  • 这种方法将复杂度从移动数据（元素移位）转移到管理关系（指针）上。

顺序数据结构对比

操作数组（目标）链式结构（目标）
随机访问$O(1)$$O(n)$（需遍历）
在位置 $i$ 的插入/删除$O(n)$（移位）$O(1)$（指针更新，一旦找到 $i$）
内存分配连续非连续（动态）